package com.xgh.middle;

import java.util.PriorityQueue;

/**
 * @ClassName TestSort
 * @Description
 * @Author xinggh
 * @Date 2020/7/31 12:38
 * @Version 1.0
 **/
public class TestSort {

    private static int partition(int[] nums, int left, int right) {
        int pivot = nums[right];

        while (left < right) {
            while (left < right && nums[left] >= pivot) {
                left++;
            }
            nums[right] = nums[left];

            while (left < right && nums[right] <= pivot) {
                right--;
            }
            nums[left] = nums[right];
        }

        nums[left] = pivot;
        return left;
    }

    public static int quick(int[] nums, int left, int right, int k) {

        int partition = partition(nums, left, right);
        if (partition == k) {
            return nums[partition];
        }

        return k > partition ? quick(nums, partition + 1, right, k) : quick(nums, left, partition - 1, k);


    }

    public static void main(String[] args) {
        int[] arr = {49, 38, 65, 97, 22};
        int quick = quick(arr, 0, arr.length - 1, 2);
        System.out.println(quick);
       /* System.out.println("排序后:");
        for (int i : arr) {
            System.out.println(i);
        }*/
    }


    public int findKthLargest(int[] nums, int k) {
        // 默认小顶堆
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>(k);
        for (int num : nums) {
            if (heap.size() < k){
                heap.offer(num);
            } else {
                if (num > heap.peek()){
                    heap.poll();
                    heap.offer(num);
                }
            }
        }
        return heap.peek();
    }



}
